1. Field of the Invention
This invention relates to a memory cache that stores instructions received from a memory and provides the instructions to a processing unit. More particularly, this invention relates to reading blocks of instructions from memory and reordering the block of instructions to provide the instructions in an optimal order to the processing unit.
2. Prior Art
In many computer systems, it is common to have a memory cache for providing instructions from a memory to a processing unit. A memory cache is a memory that stores instructions from a main memory that may be frequently reused. There are two principles which make a memory cache effective. The first principle is temporal locality which means that if one piece of data or instructions is accessed, similar data or instructions are likely to be accessed soon. The second principle is spatial locality which means that if one piece of data or an instruction is accessed, pieces of data or instructions stored nearby are likely to be accessed soon.
The memory cache provides the stored instructions to the processing unit when the instructions are requested. This eliminates a need for an Input/Output (“I/O”) event that requires additional time to retrieve the instruction from the memory that wastes processing time.
Typically, cache schemes for storing instructions are very simplistic to reduce the complexity of the circuitry needed to provide the cache. This is because performance of a cache is directly related to the complexity of the cache circuitry. In most cache systems a direct-mapped cache system is used. In a direct-mapped cache, lower bits of a physical address of an instruction or piece of data in memory used to store the instruction or data. For example, if a cache store 64 entries, instructions or pieces with data with physical addresses of A through A+64 are stored to the same entry as the instructions or pieces of data are received from memory.
Furthermore, there is no ordering of the instructions stored in the cache to provide the instructions in the likely order that the instructions will be executed by the processor. This slows retrieval of instructions from the cache, as a cache controller must make repeated searches for sequential instructions.
A more complex method for storing instructions is trace caching. In trace caching additional circuitry is added to store recently executed instructions in a buffer to provide these executed instructions quickly to the cache. Although this method greatly increases the speed at which instructions are provided, the additional circuitry increases the complexity of the cache circuitry which in turn increases the cost of the circuitry. A trace cache utilizes a special form of spatial locality. The instructions executed by a micro processor can be broken into logical structures called “Basic Blocks.” For purposes of this discussion, a basic block is a sequence of instructions that are a complete sequence that must be completed after a first instruction is executed. A trace cache uses additional circuitry to store entire blocks rather than individual instructions. This increases the efficiency of the block because the processor has to make fewer accesses to main memory to retrieve instructions in the block as execution of the block is performed.
As clock rates of processing units increase, it becomes more of a problem to design storage schemes for memory caches that quickly provide instructions to the processing unit to reduce wasted clock cycles while waiting for information to be retrieved from main memory. For purposes of the present discussion, main memory is the Random Access Memory or disk storage of a computer system. Furthermore, the complexity of the circuitry required to optimally order instructions in a microprocessor pipeline greatly increases. Therefore, those skilled in the art are constantly trying to improve the methods of storing instructions in the cache to provide instructions to the processing unit without adding additional circuitry to the critical path of the microprocessor.